package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC216 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        List<Integer> temp = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();

        public List<List<Integer>> combinationSum3(int k, int n) {
            dfs(1, 9, k, n);
            return ans;
        }

        public void dfs(int cur, int n, int k, int sum) {
            if (temp.size() + (n - cur + 1) < k || temp.size() > k) {
                return;
            }
            if (temp.size() == k) {
                int tempSum = 0;
                for (int num : temp) {
                    tempSum += num;
                }
                if (tempSum == sum) {
                    ans.add(new ArrayList<Integer>(temp));
                    return;
                }
            }
            temp.add(cur);
            dfs(cur + 1, n, k, sum);
            temp.remove(temp.size() - 1);
            dfs(cur + 1, n, k, sum);
        }
    }

    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC216 an = new LC216();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
